package dynamicProgramming.DoubleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/23 09:22
 **/
/**
 * 题目 ：子序列数目
 * 题目详述 ：
 * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
 * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
 * （例如，"ACE"是"ABCDE"的一个子序列，而"AEC"不是）
 * 题目数据保证答案符合 32 位带符号整数范围。
 *
 * 提示：
 * 0 <= s.length, t.length <= 1000
 * s 和 t 由英文字母组成
 */
public class NumDistinct02 {
    public static void main(String[] args) {
        numDistinct("babgbag" , "bag");
    }
    /**
     * 思路 ：
     * 迭代 ：动态规划实现求取字串T在主串S中出现次数
     *
     * 状态转移方程 ：
     * 即，假设f(i + 1,j + 1)为长度为j + 1的子串T在长度为i + 1的主串S所出现次数;
     * (1)若是主串的最后一个字符S[i]和子串的最后一个字符T[j]相同的话，
     * 即，可能会出现两种情况 ：a.S[i]与T[j]相互消去,即 f(i , j);b.舍去S[i],即f(i ,j + 1);
     * (2)若是主串的最后一个字符S[i]和子串的最后一个字符T[j]不相同的话，
     * 即，必然只能够舍去S[i] ===》f(i , j + 1);
     * (3)特殊情况考虑 ：
     * a.主串S和子串T皆为空字符串，f(-1 , -1) == 1;
     * b.主串S不为空 && 子串T为空的话，即f(i , -1) == 1;
     * c.主串S为空 && 主串T不为空的话，即f(-1 , j) == 0;
     * @param s
     * @param t
     * @return
     */
    public static int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();

        // 一维数组，用来存储 在计算f(i + 1,j + 1)之前的f(i,j + 1) && 在计算f(i + 1,j + 1)之后的f（i + 1，j + 1）
        int[] temp = new int[len2 + 1];
        // 特殊情况1 ：即当子串T和主串S都为空字符串的话，即字串T在主串中所出现的次数为1;
        temp[0] = 1;
        // 特殊情况2 ：f(-1 , j) == 0;由于主串S为空，只要子串T不为空的话，那么temp[0][j + 1]必然为0;

        for(int i = 0;i < len1;i++){
            /**
             * 需要注意的是 ：
             * 即，遍历主串S时 && 同时遍历子串T
             * ===》 在遍历主串S的过程中，最后prev变量所存储的是，上一次最后所遗留的f(i , j + 1);
             * 但是，所要求取的应该是 重新开启一个for(i + 1)循环，即prev变量应该重新保存f(i + 1 , 0)
             */
            int prev = temp[0];// 使用prev变量来存储f(i , j)的值;
            int cur;
            // 特殊情况3 ：f(i , -1) == 1;由于子串T为空，同时主串S不为空，所以temp[i + 1][0] == 1;
            for(int j = 0;j <= i && j < len2;j++){
                // 若是主串S的最后一个字符S[i] == 子串T的最后一个字符T[j]的话，
                // ===》(1)f(i + 1,j + 1) = f(i,j); （消去字符S[i]和T[j]）
                // 或者 (2)f(i + 1,j + 1) = f(i,j + 1);（舍弃字符S[i]）
                if(s.charAt(i) == t.charAt(j)){
                    cur = prev + temp[j + 1];
                }
                else {
                    // 若是主串S的最后一个字符S[i] != 子串T的最后一个字符T[j]的话，
                    // ===》 即，必然是f(i + 1,j + 1) = f(i,j + 1);（舍弃字符S[i]）
                    cur = temp[j + 1];
                }
                prev = temp[j + 1];
                temp[j + 1] = cur;
            }
        }
        return temp[len2];
    }
    /**
     * 分析 ：
     * 时间复杂度 ：O（mn）（其中，m为主串S的字符数量;n为子串T的字符数目）
     */
}
